A METHOD OF SYNTHESIS OF IRREDUNDANT CIRCUITS (IN A STANDARD BASIS) ADMITTING SINGLE FAULT DIAGNOSTIC TEST SETS WITH CARDINALITY 2

Romanov Dmitriy Sergeevich, Candidate of physical and mathematical sciences, associate professor, sub-department of mathematical cybernetics, Lomonosov Moscow State University (1 Leninskie gory street, Moscow, Russia), romanov@cs.msu.ru

519.718

10.21685/2072-3040-2016-3-4

Background. The aim of this work is to demonstrate that for an arbitrary Boolean function it is possible to construct a circuit (in the basis {x&y, xy, x}) realizing this function and allowing a small single fault diagnosing test set (under inverse faults on outputs of gates). It can be useful for the design of easily testable VLSI.
Materials and methods. The theory of Boolean functions and combinational circuits design methods were used.
Results. It has been established that for arbitrary Boolean function f depending on n variables there exists an irredundant combinational circuit (in the basis {x&y, xy, x}) realizing f and admitting a single fault diagnosing test set (under inverse faults on outputs of gates) with cardinality 2 or less. For every Boolean function the minimal cardinality of a single diagnostic test set has been established.

combinational circuit, fault diagnostic test set, inverse fault on output of gate, Shannon function, easily testable circuit.

1. Yablonskiy S. V., Chegis I. A. Uspekhi matematicheskikh nauk [Advances of mathematical sciences]. 1955, vol. 10, iss. 4 (66), pp. 182–184.
2. Chegis I. A., Yablonskiy S. V. Trudy matematicheskogo instituta imeni V. A. Steklova [Proceedings of the Mathematical Institute named after V.A. Steklov]. 1958, vol. 51, pp. 270–360.
3. Red'kin N. P. Nadezhnost' i diagnostika skhem [Reliability and diagnostics of circuits]. Moscow: Izd-vo MGU, 1992, 192 p.
4. Fujiwara H. Logic testing and design for testability.Cambridge; Massachusetts;London:MIT Press,1990,284p.
5. Reddy S. M. IEEE Trans. Comput. 1972, vol. 21, iss. 1, pp. 124–141.
6. Saluja K. K., Reddy S. M. IEEE Trans. Comput. 1975, vol. 24, no. 1, pp. 995–998.
7. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1986, no. 1, pp. 72–74.
8. Red'kin N. P. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1989, iss. 2, pp. 198–222.
9. Red'kin N. P. Izvestiya vuzov. Matematika [University proceedings. Mathematics]. 1988, no. 7, pp. 57–64.
10. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1988, no. 2, pp. 17–21.
11. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 1992, no. 5, pp. 43–46.
12. Red'kin N. P. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2007, no. 3, pp. 29–33.
13. Kovatsenko S. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2000, no. 2, pp. 45–47.
14. Kolyada S. S. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2011, no. 6, pp. 47–49.
15. Kolyada S. S. Diskretnyy analiz i issledovanie operatsiy [Discrete analysis and research of operations]. 2013, vol. 20, no. 2, pp. 58–74.
16. Kolyada S. S. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2013, no. 4, pp. 32–34.
17. Noskov V. N. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, iss. 4, pp. 3–23.
18. Hirayama T., Koda G., Nishitani Y., Shimizu K.IEICE Trans.Inf. & Syst.1999,vol.E-82D,no.9,pp.1278–1286.
19. Hayes J. P. IEEE Trans. Comput. 1974, vol. C-23, no. 1, pp. 56–62.
20. Saluja K. K., Reddy S. M. IEEE Trans. Comput. 1974, vol. C-23, no. 1, pp. 552–554.
21. Inose H., Sakauchi M. Proc. First USA-Japan Computer Conf. 1972, pp. 426–430.
22. DasGupta S., Hartmann C. R. P., Rudolph L. D. IEEE Trans. Comput. 1980, vol. C-29, no.11,pp.1025–1029.
23. Goryashko A. P. Avtomatika i telemekhanika [Automation and remote control]. 1981, no. 1,pp.145–153.
24. Red'kin N. P. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 2003, iss. 12, pp. 217–230.
25. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2008, no. 1, pp. 40–44.
26. Borodina Yu. V. Vestnik Moskovskogo universiteta. Ser. 1. Matematika. Mekhanika [Bulletin of Moscow University. Series 1. Mathematics. Mechanics]. 2008, no. 5, pp. 49–52.
27. Borodina Yu. V., Borodin P. A. Diskretnaya matematika [Discrete mathematics]. 2010, vol. 22, iss. 3, pp. 127–133.
28. Borodina Yu. V. Problemy teoreticheskoy kibernetiki: materialy XVII Mezhdunar. konf. (Kazan', 16–20 iyunya 2014 g.) [Problems of theoretical cybernetics: proceedings of XVII International conference (Kazan, 16th–20th June 2014)]. Kazan: Otechestvo, 2014, pp. 38–39.
29. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2013, vol. 25, iss. 2, pp. 104–120.
30. Romanov D. S. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2015, no. 1, pp. 30–37.
31. Romanov D. S. Diskretnaya matematika [Discrete mathematics]. 2014, vol. 26, iss. 2, pp. 100–130.
32. Popkov K. A. O tochnom znachenii dliny minimal'nogo edinichnogo diagnosticheskogo testa dlya odnogo klassa skhem [On the exact value of the minimal single diagnostic test set for circuits of a single class]. Moscow: Izd-vo IPM im. M. V. Keldysha RAN, 2015, 20 p.
33. Romanov D. S. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2015, no. 4 (36), pp. 38–54.
34. Von Neumann J. Automata Studies. Eds. C. Shannon and J. McCarthy. Princeton, NJ: Princeton University Press, 1956, pp. 329–378.
35. Alekhina M. A. Diskretnyy analiz i issledovanie operatsiy. Ser. 1 [Discrete analysis and research of operations. Sereis 1]. 2005, vol. 12, no. 2, pp. 3–11.
36. Alekhina M. A., Chugunova V. V. Diskretnyy analiz i issledovanie operatsiy. Ser. 1 [Discrete analysis and research of operations. Sereis 1]. 2006, vol. 13, no. 4, pp. 3–17.
37. Vasin A. V. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2008, no. 4, pp. 2–16.
38. Alekhina M. A., Vasin A. V. Uchenye zapiski Kazanskogo gosudarstvennogo universiteta. Ser. Fiz.-matem. nauki [Proceedings of Kazan State University. Sereis: physical and mathematical science]. 2009, vol. 151, bk. 2, pp. 25–35.
39. Alekhina M. A., Vasin A. V. Izvestiya vuzov. Matematika [University proceedings. Mathematics]. 2010, no. 5, pp. 79–82.
40. Alekhina M. A. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 219–225.
41. Alekhina M. A., Vasin A. V. Matematicheskie zametki [Notes on mathematics].2014,vol.95,no.2,pp.170–201.